﻿using System;
using System.Collections;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System.Text;
using System.Collections.Generic;
using System.Threading;
using System.Diagnostics;
using ArithCollect;

namespace UnitTestProject1 {
    //http://blog.csdn.net/hawksoft/article/details/7014796
    /*红黑树*/
    namespace AlbertAlgorithms {
        /// <summary>
        /// 节点颜色枚举
        /// </summary>
        public enum RBTreeNodeColor {
            Red,
            Black
        }
        /// <summary>
        /// 红黑树节点
        /// </summary>
        public class RBTreeNode {
            public int Key { get; set; }
            public RBTreeNode Left { get; set; }
            public RBTreeNode Right { get; set; }
            public RBTreeNode Parent { get; set; }
            public RBTreeNodeColor NodeColor { get; set; }
        }
        /// <summary>
        /// 红黑树
        /// </summary>
        public class RBTree {
            /// <summary>
            /// 空节点，充当哨兵
            /// </summary>
            public static readonly RBTreeNode NullNode = new RBTreeNode();
            /// <summary>
            /// 静态构造函数，哨兵为黑色.
            /// </summary>
            static RBTree() {
                NullNode.NodeColor = RBTreeNodeColor.Black;
            }
            /// <summary>
            /// 根节点，默认为NullNode.
            /// </summary>
            public RBTreeNode Root = NullNode;
            /// <summary>
            /// 插入节点,这里假设了所有的节点key不相同.
            /// </summary>
            /// <param name="Node"></param>
            public void InsertNode(RBTreeNode Node) {
                ///寻找插入节点的插入点（父节点）theY.TheX是循环中间变量.
                RBTreeNode theY = NullNode;
                RBTreeNode theX = Root;
                //注意，如果不为空，则找到的插入节点一定是最底层内节点，仅有空字节点(哨兵节点).
                //这也是红黑树不是高度平衡树的一个重要原因.但这样简化了插入，不用判断补缺.
                while (theX != NullNode) {
                    theY = theX;
                    if (Node.Key > theX.Key) {
                        theX = theX.Right;
                    } else {
                        theX = theX.Left;
                    }
                }
                //将插入节点的父节点指向theY.
                Node.Parent = theY;
                //如果theY为空，则原来是空树，则新插入的节点是根节点.
                if (theY == NullNode) {
                    Root = Node;
                } else {
                    //如果有根节点，与theY的Key比较，大于则作为右子节点，小于则
                    //作为左节点.
                    if (Node.Key > theY.Key) {
                        Node.Parent = theY.Right;
                    } else {
                        Node.Parent = theY.Left;
                    }
                }
                //开始插入的节点都在非空叶子节点上，将空节点作为其两个子节点.
                Node.Right = NullNode;
                Node.Left = NullNode;
                //颜色置为红，然后整理.
                Node.NodeColor = RBTreeNodeColor.Red;
                RBInsertFixup(Node);
            }
            /// <summary>
            /// 红黑树的插入整理，以保持红黑树性质：非红即白；根和叶子黑；相邻节点不能同为红；
            /// 所有从根到叶子路径上的黑节点(黑度)相同.这里的相邻只会是父子节点间，书上的定义是
            /// 红节点的两个孩子节点都是黑的，表达是等价的.从根到叶子节点看做是树的路径，则路径
            /// 上红节点不能相邻.
            /// </summary>
            /// <param name="Node"></param>
            private void RBInsertFixup(RBTreeNode Node) {
                //因为当前节点为红色，从下向根方向整理，如果当前节点的父节点为红色，则违反了红黑树的性质，
                //就需要不断整理，直到当前整理节点的父节点是黑色为止.整理一定会有结束条件，
                //因为根节点肯定为黑。
                while (Node.Parent.NodeColor == RBTreeNodeColor.Red) {
                    //如果父节点为红色，则爷节点必为黑色（红黑树性质）。
                    //如果当前节点的父节点是左孩子
                    if (Node.Parent == Node.Parent.Parent.Left) {
                        //找到其叔父节点.
                        RBTreeNode theY = Node.Parent.Parent.Right;
                        //如果叔父节点是红色节点，而爷节点为黑色节点。形式就是爷节点为黑，父辈节点为红，由于当前节点为红，
                        //父节点必须改为黑色。而且这种改变不能影响黑度(所有从根到叶子节点的路径中黑节点数相等），那么改变的策略
                        //就是将爷节点变为红色，父辈节点变为黑色，这种改变显然没有改变路径上的黑度。但因为爷节点变为了红色，可能
                        //会导致红黑树性质的改变,就需要继续整理，因此需将整理节点上移到爷节点，继续整理。
                        if (theY.NodeColor == RBTreeNodeColor.Red) {
                            Node.Parent.NodeColor = RBTreeNodeColor.Black;
                            theY.NodeColor = RBTreeNodeColor.Black;
                            Node.Parent.Parent.NodeColor = RBTreeNodeColor.Red;
                            Node = Node.Parent.Parent;
                        }
                            //如果叔父节点是黑色，爷节点也为黑色，父节点因为要改成黑节点，就增加了当前节点路径上的黑度。因此处理就稍微复杂些。
                        else {
                            //如果当前节点是右孩子，先左旋。因为轴是当前节点和父节点，都为红色，因此左旋不会改变黑度，这很关键。
                            if (Node == Node.Parent.Right) {
                                Node = Node.Parent;
                                LeftRotate(Node);
                            }
                            //将父节点改为黑节点，爷节点改为红色节点，当前节点路径上的黑度没变，但叔父路径上的黑度被减了1，为了保持黑度不变，因此需要右旋
                            //其实就是将父节点上升到爷节点，原来的爷节点降为叔父节点，这样黑度就平衡了。
                            Node.Parent.NodeColor = RBTreeNodeColor.Black;
                            Node.Parent.Parent.NodeColor = RBTreeNodeColor.Red;
                            RightRotate(Node.Parent.Parent);
                        }
                    }//如果当前节点的父节点是右孩子.因为是对称情况，所以逻辑处理与前面类似.
                    else {
                        //找到其叔父节点.
                        RBTreeNode theY = Node.Parent.Parent.Left;
                        if (theY.NodeColor == RBTreeNodeColor.Red) {
                            Node.Parent.NodeColor = RBTreeNodeColor.Black;
                            theY.NodeColor = RBTreeNodeColor.Black;
                            Node.Parent.Parent.NodeColor = RBTreeNodeColor.Red;
                            Node = Node.Parent.Parent;
                        } else {
                            if (Node == Node.Parent.Left) {
                                Node = Node.Parent;
                                RightRotate(Node);
                            }
                            Node.Parent.NodeColor = RBTreeNodeColor.Black;
                            Node.Parent.Parent.NodeColor = RBTreeNodeColor.Red;
                            LeftRotate(Node.Parent.Parent);
                        }
                    }
                }
                //保证根节点为黑色.保证下次while循环可正常结束.
                Root.NodeColor = RBTreeNodeColor.Black;
            }
            /// <summary>
            /// 对一般情况，可以分4种情况考虑：
            /// 1）无孩子，则可直接删除；
            /// 2）只有左孩子:那么只要用左孩子替换当前节点即可;
            /// 3)只有右孩子：那么只要用左孩子替换当前节点即可;
            /// 4）如果有两个孩子：则必须找到当前节点的后继节点y.y要么没孩子，要么只有右孩子。可把把当前节点与y交互信息（key和卫星数据).
            /// 然后删除y（情况1..3).如果Y的颜色为黑色，因为y的删除破坏了红黑树性质，则需要重新整理，如果y是红色的，则删除不会改变
            /// 红黑树的性质.
            /// </summary>
            /// <param name="Node"></param>
            public void RBTreeDelete(RBTreeNode Node) {
                //默认theY指向当前节点.
                RBTreeNode theY = Node;
                //如果节点的左右子孩子都不为空，则需找到当前节点的后继节点,theY指向当前节点的后继节点.
                //注意这种情况下，当前节点的后继节点一定是右孩子的最小key节点.而且theY不可能有左孩子。
                if (Node.Right != NullNode && Node.Left != NullNode) {
                    theY = GetSuccessor(Node);
                }
                RBTreeNode theX = NullNode;
                //theY.Left如果不为空，则theY就是指向Node节点，且没有右孩子.
                //如果theY没有左孩子，则theX指向theY的右孩子，注意theX也可能为空.
                if (theY.Left != NullNode) {
                    theX = theY.Left;
                } else {
                    theX = theY.Right;
                }
                //开始删除theY.
                theX.Parent = theY.Parent;
                //如果theY.Parent为空，则删除的是根节点，那么theX就变成了根节点。
                if (theY.Parent == NullNode) {
                    Root = theX;
                } else {
                    if (theY == theY.Parent.Left) {
                        theY.Parent.Left = theX;
                    } else {
                        theY.Parent.Right = theX;
                    }
                }
                //如果是theY不是指向当前节点，则表明是当前节点有两个孩子的情况，需交互数据.
                if (theY != Node) {
                    Node.Key = theY.Key;
                    //注意这里还序号拷贝卫星数据.
                }
                //如果删除的是黑节点，则必须重新整理（黑度发生变化，破坏了红黑树性质).
                if (theY.NodeColor == RBTreeNodeColor.Black) {
                    RBTreeDelFixup(theX);
                }
            }
            /// <summary>
            /// 红黑书删除整理.因为删除的节点是黑色，则由此往上需要平衡黑度.
            /// </summary>
            /// <param name="Node"></param>
            public void RBTreeDelFixup(RBTreeNode Node) {
                while (Node != Root && Node.NodeColor == RBTreeNodeColor.Black) {
                    //如果是左孩子
                    if (Node == Node.Parent.Left) {
                        RBTreeNode theW = Node.Parent.Right;
                        //兄弟节点是红色，父节点必然是黑色，这时可以通过将兄弟节点置为黑色，父节点置为红色,
                        //然后左旋,右孩子保持黑度不变，左孩子黑度还是少1，便于继续处理。.
                        if (theW.NodeColor == RBTreeNodeColor.Red) {
                            theW.NodeColor = RBTreeNodeColor.Black;
                            Node.Parent.NodeColor = RBTreeNodeColor.Red;
                            LeftRotate(Node.Parent);
                            theW = Node.Parent.Right;
                        }
                        //如果兄弟节点的左右孩子都是黑色，则可将兄弟节点置为红色，将需要平衡的节点上移后，还保持要平衡节点
                        //的黑度少1
                        if (theW.Left.NodeColor == RBTreeNodeColor.Black && theW.Right.NodeColor == RBTreeNodeColor.Black) {
                            theW.NodeColor = RBTreeNodeColor.Red;
                            Node = Node.Parent;
                        } else {
                            //如果兄弟节点的孩子有一个是红色的，则可以通过调整就可以达到这种平衡.
                            if (theW.Right.NodeColor == RBTreeNodeColor.Black) {
                                theW.Left.NodeColor = RBTreeNodeColor.Black;
                                theW.NodeColor = RBTreeNodeColor.Red;
                                RightRotate(theW);
                                theW = Node.Parent.Right;
                            }
                            theW.NodeColor = Node.Parent.NodeColor;
                            Node.Parent.NodeColor = RBTreeNodeColor.Black;
                            theW.Right.NodeColor = RBTreeNodeColor.Black;
                            LeftRotate(Node.Parent);
                            Node = Root;
                        }
                    } else {
                        RBTreeNode theW = Node.Parent.Left;
                        //兄弟节点是红色，父节点必然是黑色，这时可以通过将兄弟节点置为黑色，父节点置为红色,
                        //然后右旋,左孩子保持黑度不变，右孩子黑度还是少1，便于继续处理。.
                        if (theW.NodeColor == RBTreeNodeColor.Red) {
                            theW.NodeColor = RBTreeNodeColor.Black;
                            Node.Parent.NodeColor = RBTreeNodeColor.Red;
                            RightRotate(Node.Parent);
                            theW = Node.Parent.Left;
                        }
                        //如果兄弟节点的左右孩子都是黑色，则可将兄弟节点置为红色，将需要平衡的节点上移后，还保持要平衡节点
                        //的黑度少1
                        if (theW.Left.NodeColor == RBTreeNodeColor.Black && theW.Right.NodeColor == RBTreeNodeColor.Black) {
                            theW.NodeColor = RBTreeNodeColor.Red;
                            Node = Node.Parent;
                        } else {
                            //如果兄弟节点的孩子有一个是红色的，则可以通过调整就可以达到这种平衡.
                            if (theW.Left.NodeColor == RBTreeNodeColor.Black) {
                                theW.Left.NodeColor = RBTreeNodeColor.Black;
                                theW.NodeColor = RBTreeNodeColor.Red;
                                LeftRotate(theW);
                                theW = Node.Parent.Left;
                            }
                            theW.NodeColor = Node.Parent.NodeColor;
                            Node.Parent.NodeColor = RBTreeNodeColor.Black;
                            theW.Left.NodeColor = RBTreeNodeColor.Black;
                            RightRotate(Node.Parent);
                            Node = Root;
                        }

                    }

                }
                Node.NodeColor = RBTreeNodeColor.Black;
            }
            /*所谓二叉树的旋转，其实可以这样理解，当前节点c,和其孩子l,r.看做是滑轮上的三个点，C在滑轮上的支点，l,r分别吊在
             滑轮的两边。左旋的结果就是右边得孩子到了滑轮支点，C向左下滑，右旋则相反，这种旋转，目的就是保持某种平衡。比如右边孩子
             * 如果重了，就会引起不平衡，就需要左旋，当然，因为要保持查找树的性质，左右孩子(l,r)的子节点需要做一定调整.*/
            /// <summary>
            /// 左旋，以当前节点和其右孩子为轴。
            /// </summary>
            /// <param name="Node"></param>
            private void LeftRotate(RBTreeNode Node) {
                RBTreeNode theY = Node.Right;
                Node.Right = theY.Left;
                theY.Left.Parent = Node;
                if (Node.Parent == NullNode) {
                    Root = theY;
                } else if (Node == Node.Parent.Left) {
                    Node.Parent.Left = theY;
                } else {
                    Node.Parent.Right = theY;
                }
                theY.Left = Node;
                Node.Parent = theY;

            }
            /// <summary>
            /// 右旋，以当前节点和其左孩子为轴.
            /// </summary>
            /// <param name="Node"></param>
            private void RightRotate(RBTreeNode Node) {
                RBTreeNode theY = Node.Left;
                Node.Left = theY.Right;
                theY.Right.Parent = Node;
                if (Node.Parent == NullNode) {
                    Root = theY;
                } else if (Node == Node.Parent.Left) {
                    Node.Parent.Left = theY;
                } else {
                    Node.Parent.Right = theY;
                }
                theY.Right = Node;
                Node.Parent = theY;
            }
            /// <summary>
            /// 查找树的节点.
            /// </summary>
            /// <param name="Key">关键值.</param>
            /// <returns></returns>
            public RBTreeNode TreeSearch(int Key) {
                RBTreeNode theX = Root;
                while (theX != NullNode && theX.Key != Key) {
                    if (theX.Key < Key) {
                        theX = theX.Right;
                    } else {
                        theX = theX.Left;
                    }
                }
                return theX;
            }
            /// <summary>
            /// 获取以Node为根节点的子树的最小关键值节点
            /// </summary>
            /// <returns></returns>
            public RBTreeNode GetMinKeyNode(RBTreeNode Node) {
                RBTreeNode theX = Node;
                while (theX != NullNode) {
                    theX = theX.Left;
                }
                return theX;
            }
            /// <summary>
            /// 获取以指定节点为根的子树的最大关键值节点
            /// </summary>
            /// <returns></returns>
            public RBTreeNode GetMaxKeyNode(RBTreeNode Node) {
                RBTreeNode theX = Node;
                while (theX != NullNode) {
                    theX = theX.Right;
                }
                return theX;
            }
            /// <summary>
            /// 寻找指定节点的后继节点.
            /// </summary>
            /// <param name="node"></param>
            /// <returns></returns>
            public RBTreeNode GetSuccessor(RBTreeNode Node) {
                //如果当前节点右孩子不为空，则后续节点显然是右孩子子树的最小节点。
                if (Node.Right != NullNode) {
                    return GetMinKeyNode(Node.Right);
                }
                RBTreeNode theF = Node.Parent;
                //如果当前节点的右孩子为空，则从其父节点开始判断，如果当前节点是其父节点的左孩子，则后续节点就是父节点.
                //如果是右孩子，则继续向上寻找，直到为空或者当前节点是其父节点的左孩子为止.
                while (theF != NullNode && Node != theF.Right) {
                    Node = theF;
                    theF = theF.Parent;
                }
                return theF;
            }
            /// <summary>
            /// 寻找指定节点的继节点.
            /// </summary>
            /// <param name="node"></param>
            /// <returns></returns>
            public RBTreeNode GetPredecessor(RBTreeNode Node) {
                //如果当前节点左孩子不为空，则后续节点显然是左孩子子树的最大节点。
                if (Node.Left != NullNode) {
                    return GetMaxKeyNode(Node.Left);
                }
                RBTreeNode theF = Node.Parent;
                //如果当前节点的左孩子为空，则从其父节点开始判断，如果当前节点是其父节点的右孩子，则后续节点就是父节点.
                //如果是左孩子，则继续向上寻找，直到为空或者当前节点是其父节点的右孩子为止.
                while (theF != NullNode && Node != theF.Left) {
                    Node = theF;
                    theF = theF.Parent;
                }
                return theF;
            }
        }

    }
    /*性能测试代码Code highlighting produced by Actipro CodeHighlighter (freeware)
        http://www.CodeHighlighter.com/-->using 
     */
    namespace DictionaryTest {
        [TestClass]
        public class Program {
            [TestMethod]
            public void CTest1() {
                var total = 100000;
                ushort target = 10000;
                var x = total.AdagunSet().ToArray();
                var x2 = target.UnrepeatSet(total + 50000).ToArray();
                var x3 = new Random().Next(total);
                SortedDictionaryTest(x, x2, x3);
                DictionaryTest(x, x2, x3);
                SortedListTest(x, x2, x3);
                HashtableTest(x, x2, x3);
            }

            private static void SortedListTest(int[] x, int[] x2, int x3) {
                var ht = new SortedList();
                Stopwatch watch = new Stopwatch();
                watch.Start();
                foreach (var item in x) {
                    ht.Add(item, item);
                }
                watch.Stop();
                Console.WriteLine(string.Format("SortedList添加{0}个元素耗时：{1}ms", x.Length, watch.ElapsedMilliseconds));
                watch.Reset();
                watch.Start();
                foreach (var item in x2) {
                    //Console.WriteLine("value:{0},?{1}",item,ht.ContainsKey(item));
                    ht.ContainsValue(item);
                }
                watch.Stop();
                Console.WriteLine(string.Format("SortedList查找在100000个元素中查找随机的{0}个的元素耗时：{1}ms", x2.Length, watch.ElapsedMilliseconds));
                ht.Clear();
            }
            private static void HashtableTest(int[] x, int[] x2, int x3) {
                Hashtable ht = new Hashtable();
                Stopwatch watch = new Stopwatch();
                watch.Start();
                foreach (var item in x) {
                    ht.Add(item, item);
                }
                watch.Stop();
                Console.WriteLine(string.Format("Hashtable添加{0}个元素耗时：{1}ms", x.Length, watch.ElapsedMilliseconds));
                watch.Reset();
                watch.Start();
                foreach (var item in x2) {
                    //Console.WriteLine("value:{0},?{1}",item,ht.ContainsKey(item));
                    ht.ContainsKey(item);
                    //ht.ContainsValue(item);
                }
                watch.Stop();
                Console.WriteLine(string.Format("Hashtable查找在100000个元素中查找随机的{0}个的元素耗时：{1}ms", x2.Length, watch.ElapsedMilliseconds));
                ht.Clear();
            }

            private static void DictionaryTest(int[] x, int[] x2, int x3) {
                Dictionary<int, int> ht = new Dictionary<int, int>();
                Stopwatch watch = new Stopwatch();
                watch.Start();
                foreach (var item in x) {
                    ht.Add(item, item);
                }
                watch.Stop();
                Console.WriteLine(string.Format("Dictionary添加{0}个元素耗时：{1}ms", x.Length, watch.ElapsedMilliseconds));
                watch.Reset();
                watch.Start();
                foreach (var item in x2) {
                    //Console.WriteLine("value:{0},?{1}", item, ht.ContainsKey(item));
                    ht.ContainsKey(item);
                    //ht.ContainsValue(item);
                }
                watch.Stop();
                Console.WriteLine(string.Format("Dictionary查找在100000个元素中查找随机的{0}个的元素耗时：{1}ms", x2.Length, watch.ElapsedMilliseconds));
                ht.Clear();
            }

            private static void SortedDictionaryTest(int[] x, int[] x2, int x3) {
                SortedDictionary<int, int> ht = new SortedDictionary<int, int>();
                Stopwatch watch = new Stopwatch();
                watch.Start();
                foreach (var item in x) {
                    ht.Add(item, item);
                }
                watch.Stop();
                Console.WriteLine(string.Format("SortedDictionary添加{0}个元素耗时：{1}ms", x.Length, watch.ElapsedMilliseconds));
                watch.Reset();
                watch.Start();
                foreach (var item in x2) {
                    //Console.WriteLine("value:{0},?{1}", item, ht.ContainsKey(item));
                    ht.ContainsKey(item);
                    //ht.ContainsValue(item);
                }
                watch.Stop();
                Console.WriteLine(string.Format("SortedDictionary查找在100000个元素中查找随机的{0}个的元素耗时：{1}ms", x2.Length, watch.ElapsedMilliseconds));
                ht.Clear();
            }
        }
    }
    //http://zhidao.baidu.com/link?url=KU_q43fH1VES7jPIwGi0zUnkhYMZBR5jJKjykuamDA4JHRQ7b_SE2H7KD5cfDqhKMlgzctFcR8CGy3Qy_9Um1q
    namespace ParticalTest2 {
        [TestClass]
        public class PTest {
            [TestMethod]
            public void MyTestMethod() {
                PSO p = new PSO();
                p.mains();
                System.Console.ReadLine();
            }
        }
        class PSO {
            const int S = 20; /*试验次数 */
            const int G = 2000;  /*混合迭代次数*/
            const int P = 40; /*个体总数*/
            const int V = 30; /*个体维数*/
            const double MAX = 5.12;
            const double MIN = -5.12;
            double D = MAX; /*蛙跳的最大值*/
            int i1, i2, i3, i4;
            int try_number = 0;
            int try_max = 5;
            double R;//0-1之间的随机数,精度为1/10000
            double Wmax = 0.9;
            double Wmin = 0.4;
            double PI = 3.14159265;
            double W = 0.9;
            double c1 = 2.0;/*学习因子1*/
            double c2 = 2.0;/*学习因子2*/
            double Vpso = 0.0;
            double Tolerance = 0.0000001;//收敛精度
            double c3 = 0.03;//扰动幅度
            double e = 2.718281828459;//自然对数底数
            int sm = 3;
            int bz = 0;//扰动因子标志
            public class Individal {
                public double[] d = new double[V];
                public double fitness;
            }
            public class Psom {
                public double[] sd = new double[V];
            }
            public Psom[] pso = new Psom[P];                   /*记录每个离子各位的更新速度*/
            public Individal px;                               /*全体中最好位置*/
            public Individal[] individual = new Individal[P];  /*全部个体*/
            public Individal[] individuala = new Individal[P]; /*全部个体——备份*/
            public Individal tem;
            public PSO() {
                for (int i = 0; i < P; i++) {
                    pso[i] = new Psom();
                    individual[i] = new Individal();
                    individuala[i] = new Individal();
                }
            }
            /*选择测试函数为Sphere*/
            /*选择测试函数为Sphere*/
            public double fitness(double[] a) {
                int i;
                double sum = 0.0;
                double sum1 = 0.0;
                double s1 = 0.0, h1 = 0.0;
                double[] x1 = new double[V + 1];
                for (i = 0; i < V; i++) x1[i] = a[i];
                for (i = 0; i < V; i++)
                    for (i = 0; i < V; i++)
                        sum = sum + (x1[i] * x1[i] - 10 * Math.Cos(2 * PI * x1[i]) + 10); return sum;
            }
            /*对每一个个体初始化*/
            public void init() {
                Random ran = new Random();
                //R = ran.NextDouble();                
                int i, j, pmin = 0;
                //srand((unsigned)time(NULL));
                for (i = 0; i < P; i++) {
                    for (j = 0; j < V; j++) {
                        R = ran.NextDouble();
                        individual[i].d[j] = R * (MAX - MIN) + MIN;
                    }
                    individual[i].fitness = fitness(individual[i].d);//计算初始适应值
                    individuala[i] = individual[i];//将个体复制给另一个序列
                }
                for (i = 0; i < P - 1; i++) {
                    if (individual[pmin].fitness > individual[i + 1].fitness)
                        pmin = i + 1;//适应值小者最优
                }
                px = individual[pmin];//最优者为小
            }
            /*按照适应度降序对全部个体进行排序和族群划分*/
            /*群组内更新*/
            public void update() {
                int i, j, k, l, n;
                double a;
                double b;
                W = Wmax - (double)(i2) * (Wmax - Wmin) / (double)(G);
                for (i = 0; i < P; i++) {
                    for (j = 0; j < V; j++)//更新粒子速度、位置
                    {//更新速度
                        pso[i].sd[j] = W * pso[i].sd[j] + c1 * R * (individuala[i].d[j] - individual[i].d[j]) + c2 * R * (px.d[j] - individual[i].d[j]);
                        if (pso[i].sd[j] > D) pso[i].sd[j] = D; //D 最大速度
                        if (pso[i].sd[j] < -D) pso[i].sd[j] = -D;
                        individual[i].d[j] = individual[i].d[j] + pso[i].sd[j];//更新位置
                    }
                    a = fitness(individual[i].d);//计算本次迭代的粒子适应值
                    // printf("old是%.16f",individual[i].fitness);
                    individual[i].fitness = a;
                    // printf("new是%.16f",individual[i].fitness);
                    // getchar();
                    if (a < individuala[i].fitness) {
                        individuala[i] = individual[i];
                        if (individuala[i].fitness < px.fitness)
                            px = individuala[i];
                    }//比较粒子与前一次迭代的适应值 寻求最优者
                }
            }
            public void report() {
                int i;
                System.Console.WriteLine(px.fitness);
                for (i = 0; i < P; i++) {
                    // printf("%.16f\n",individual[i].fitness);
                    // printf("%.16f\n",individuala[i].fitness);
                }
            }
            public void mains() {
                // int i1,i2;
                //clock_t start, end;
                double ave;
                //FILE* f = fopen("result(SFLA).txt", "w");
                //for(i4=0;i4<G+1;i4+=50)
                //{ 
                ave = 0.0;
                //start = clock();
                for (int i1 = 0; i1 < S; i1++) {
                    init();
                    for (int i2 = 0; i2 < G; i2++) {
                        update();
                        // report();
                        //  getchar();
                    }
                    //
                    //
                    report();
                    ave = ave + px.fitness;
                }
                //end = clock();
                ave = ave / S;
                System.Console.WriteLine("平均极值为:");
                System.Console.WriteLine(ave);
                //System.Console.WriteLine("Interval=%.2fseconds\n", (double)(end - start) / ((double)CLOCKS_PER_SEC));
                //printf("%d代为平均极值为%.16f\n",i4,ave);
                //fprintf(f,"%d代为平均极值为%.16f\n",i4,ave);
                // getchar();   
                //getchar();
            }
        }
    }
    //http://blog.csdn.net/ma_jiang/article/details/5057753
    namespace SEI.DL88250.SourceCodes.BinaryTree {
        ///   <summary> 二叉树节点类 </summary> 
        class TreeNode {
            ///   <summary> 当前节点的出现计数 </summary> 
            private int _occurs;
            ///   <summary> 当前节点值 </summary> 
            private object _nval;
            ///   <summary> 左孩子节点 </summary> 
            private TreeNode _lchild;
            ///   <summary> 右孩子节点 </summary> 
            private TreeNode _rchild;

            ///   <value> 设置/返回右孩子节点 </value> 
            ///   <remarks> 设置/返回
            ///   <see cref="_rchild"/> 字段
            ///   </remarks> 
            public TreeNode RightChild {
                get { return _rchild; }
                set { _rchild = (TreeNode)value; }
            }

            ///   <value> 设置/返回左孩子节点 </value> 
            ///   <remarks> 设置返回
            ///   <see cref="_lchild"/> 字段
            ///   </remarks> 
            public TreeNode LeftChild {
                get { return _lchild; }
                set { _lchild = (TreeNode)value; }
            }

            ///   <value> 返回当前节点值 </value> 
            ///   <remarks> 返回
            ///   <see cref="_nval"/> 字段
            ///   </remarks> 
            public object Value { get { return _nval; } }

            ///   <summary> 构造一个二叉树节点 </summary> 
            ///   <param name="val"> 节点对象 </param> 
            public TreeNode(object val) {
                _nval = val;
                _occurs = 1;
                _rchild = _lchild = null;
            }

            ///   <summary> 在二叉树中查找指定对象 </summary> 
            ///   <param name="val"> 待查对象 </param> 
            ///   <remarks> 用尾递归方式进行查找 </remarks> 
            ///   <returns> 
            ///      <list> 
            ///          <item> null: 说明未找到待查对象 </item> 
            ///          <item> this: 待查对象 </item> 
            ///          <item> _lchild.FindValue(val): 左子树递归查找 </item> 
            ///          <item> _rchild.FindValue(val): 右子树递归查找 </item> 
            ///      </list> 
            ///   </returns> 
            public TreeNode FindValue(object val) {
                IComparable ic = val as IComparable;

                if (0 == ic.CompareTo(_nval)) { //  找到！ 
                    return this;
                }

                if (ic.CompareTo(_nval) < 0) { //  到左子树中查找 
                    if (null == _lchild) {
                        return null;
                    }
                    return _lchild.FindValue(val);
                } else //  到右子树中查找 
            {
                    if (null == _rchild) {
                        return null;
                    }
                    return _rchild.FindValue(val);
                }
            }

            ///   <summary> 插入对象到二叉树中 </summary> 
            ///   <remarks> 用尾递归方式进行插入 </remarks> 
            ///   <param name="val"> 要插入的对象 </param> 
            public void InsertValue(object val) {
                IComparable ic = val as IComparable;

                if (0 == ic.CompareTo(_nval)) {
                    _occurs++;
                    return;
                }

                if (ic.CompareTo(_nval) < 0) { //  插入到左子树 
                    if (null == _lchild) {
                        _lchild = new TreeNode(val);
                    } else {
                        _lchild.InsertValue(val);
                    }
                } else { //  插入到右子树  
                    if (null == _rchild) {
                        _rchild = new TreeNode(val);
                    } else {
                        _rchild.InsertValue(val);
                    }
                }
            }

            ///   <summary> 设置左子树叶子节点为指定对象值 </summary> 
            ///   <remarks> 这个方法主要用于删除节点的操作 </remarks> 
            ///   <param name="leaf"> 要设置的节点值 </param> 
            ///   <param name="subtree"> 左子树根节点 </param> 
            public static void LchildLeaf(TreeNode leaf, TreeNode subtree) {
                while (subtree._lchild != null) {
                    subtree = subtree._lchild;
                }
                subtree._lchild = leaf;
            }

            ///   <summary> 删除指定对象 </summary> 
            ///   <remarks> 用尾部递归方式删除 </remarks> 
            ///   <param name="val"> 要删除的对象 </param> 
            ///   <param name="prev"> 要删除节点的前一个节点 </param> 
            ///   <returns> 
            ///      <list> 
            ///          <item> false: 说明未找到待删除对象 </item> 
            ///          <item> _lchild.RemoveValue(val, ref _lchild): 左子树递归删除 </item> 
            ///          <item> _rchild.RemoveValue(val, ref _rchild): 右子树递归删除 </item> 
            ///      </list> 
            ///   </returns> 
            public bool RemoveValue(object val, ref  TreeNode prev) {
                IComparable ic = val as IComparable;
                if (0 == ic.CompareTo(_nval)) {
                    if (_rchild != null) {
                        prev = _rchild;
                        if (_lchild != null) {
                            if (null == prev._lchild) {
                                prev._lchild = _lchild;
                            } else {
                                LchildLeaf(_lchild, prev._lchild);
                            }
                        }
                    } else {
                        prev = _lchild;
                    }
                }

                if (ic.CompareTo(_nval) < 0) {
                    if (null == _lchild) {
                        return false;
                    }
                    return _lchild.RemoveValue(val, ref  _lchild);
                } else {
                    if (null == _rchild) {
                        return false;
                    }
                    return _rchild.RemoveValue(val, ref  _rchild);
                }
            }
        }
        ///   <summary> 二叉树类 </summary> 
        class BinaryTree {
            ///   <summary> 节点类型 </summary> 
            private Type _elemType;
            ///   <summary> 根节点 </summary> 
            private TreeNode _root;
            ///   <summary> 插入一个节点到二叉树中 </summary> 
            ///   <param name="elem"> 待插入的节点 </param> 
            public void Insert(object elem) {
                //  判断是否是根节点 
                if (null == _root) {
                    ConfirmComparable(elem);
                    _elemType = elem.GetType();
                    _root = new TreeNode(elem);
                } else { //  是叶子节点 
                    ConfirmType(elem);
                    _root.InsertValue(elem);
                }
            }
            ///   <summary> 删除根节点 </summary> 
            ///   <returns> 
            ///      <list> 
            ///          <item> false: 说明当前树为空 </item> 
            ///          <item> ture: 删除根节点成功 </item> 
            ///      </list> 
            ///   </returns> 
            private bool RemoveRoot() {
                if (null == _root) {
                    return false;
                }
                TreeNode tmp = _root;
                if (_root.RightChild != null) {
                    _root = _root.RightChild;
                    TreeNode lc = tmp.LeftChild;
                    TreeNode newlc = _root.LeftChild;

                    if (lc != null) {
                        if (null == newlc) {
                            _root.LeftChild = lc;
                        } else {
                            TreeNode.LchildLeaf(lc, newlc);
                        }
                    }
                } else {
                    _root = _root.LeftChild;
                }
                return true;
            }
            ///   <summary> 删除指定对象的节点 </summary> 
            ///   <param name="elem"> 给定对象 </param> 
            ///   <returns> 
            ///      <list> 
            ///          <item> false: 说明当前树为空 </item> 
            ///          <item> _root.RemoveValue(elem, ref _root): 尾部递归删除节点 </item> 
            ///      </list> 
            ///   </returns> 
            public bool Remove(object elem) {
                if (_root == null) {
                    return false;
                }
                IComparable ic = ConfirmComparable(elem);
                ConfirmType(elem);

                if (0 == ic.CompareTo(_root.Value)) {
                    return RemoveRoot();
                }
                return _root.RemoveValue(elem, ref  _root);
            }
            ///   <summary> 查找与给定对象相同的节点 </summary> 
            ///   <param name="elem"> 给定对象 </param> 
            ///   <returns> 
            ///      <list> 
            ///          <item> null: 说明没有找到 </item> 
            ///          <item> _root.FindValue(elem): 尾部递归查找方法 </item> 
            ///      </list> 
            ///   </returns> 
            public TreeNode Find(object elem) {
                if (null == _root) {
                    return null;
                }
                ConfirmType(elem);
                return _root.FindValue(elem);
            }
            ///   <summary> 查看给定对象类型是否与二叉树节点类型相同 </summary> 
            ///   <remarks> 类型不符合的话将抛出异常 </remarks> 
            ///   <param name="elem"> 给定对比的对象 </param> 
            private void ConfirmType(object elem) {
                if (_elemType != elem.GetType()) {
                    string msg = " Element's type not match with the root's:  "
                        + _elemType.ToString();
                    throw new ArgumentException(msg);
                }
            }
            ///   <summary> 查看给定对象类型是否可以进行比较运算 </summary> 
            ///   <remarks> 如果类型不可进行比较运算的话将抛出异常 </remarks> 
            ///   <param name="elem"> 给定对象 </param> 
            ///   <returns> 
            ///   <para> IComparable: IComparable接口 </para> 
            ///   </returns> 
            private IComparable ConfirmComparable(object elem) {
                IComparable ic = elem as IComparable;
                if (null == ic) {
                    string msg = " Element type must support IComparable --  "
                           + elem.GetType().Name
                           + "  does not currently do so! ";
                    throw new ArgumentException(msg);
                }
                return ic;
            }
        }
        ///   <summary> 用于测试二叉树类 </summary> 
        [TestClass]
        public class TestBinTree {
            [TestMethod]
            public void BinTreeTest1() {
                BinaryTree bt = new BinaryTree();
                bt.Insert(" d ");
                bt.Insert(" ab ");
                bt.Insert(" a ");
                bt.Insert(" e ");
                TreeNode tn = bt.Find(" ab ");
                Console.Write(tn.Value);
                bt.Remove(" ab ");
                TreeNode tnn = bt.Find(" ab ");
                //Console.Write(tnn??"that's null");
            }
            [TestMethod]
            public void BinTreeTest2() {
                var bt = new ArithCollect.BinFinderTree<string>();
                bt.Add("a");
                bt.Add("ab");
                bt.Add("b");
                bt.Add("c");
                bt.Add("e");
                bt.Add("eed");
                Console.WriteLine("索引2处的结点值为:{0}", bt[2].Data);
                Console.WriteLine("打印索引2处结点的路径:{0}", bt.GetPath(bt[2]));
                bt.Remove(bt[2]);
                Console.WriteLine("删除索引2后的结点值为:{0}", bt[2].Data);
                Console.WriteLine("打印索引2处结点的路径:{0}", bt.GetPath(bt[2]));
                Console.WriteLine("打印值为ab的路径:{0}", bt.GetPath("ab")[0]);
                Console.WriteLine("打印值为e的路径:{0}", bt.GetPath("e")[0]);
                Console.WriteLine("打印值为eed的路径:{0}", bt.GetPath("eed")[0]);
                Console.WriteLine("\"a\".CompareTo(\"b\")={0}", "a".CompareTo("b"));
                Console.WriteLine("\"b\".CompareTo(\"c\")={0}", "b".CompareTo("c"));
                Console.WriteLine("\"a\".CompareTo(\"c\")={0}", "a".CompareTo("c"));
                Console.WriteLine("\"c\".CompareTo(\"a\")={0}", "c".CompareTo("a"));
                Console.WriteLine("\"a\".CompareTo(\"ab\")={0}", "a".CompareTo("ab"));
            }
            [TestMethod]
            public void BinTreeTest3() {
                var bt = new ArithCollect.AvlTree<string>();
                bt.Add("a");
                bt.Add("ab");
                bt.Add("b");
                bt.Add("c");
                bt.Add("e");
                bt.Add("eed");
                Console.WriteLine("索引2处的结点值为:{0}", bt[2].Data);
                Console.WriteLine("打印索引2处结点的路径:{0}", bt.GetPath(bt[2]));
                //bt.Remove(bt[2]);
                Console.WriteLine("删除索引2后的结点值为:{0}", bt[2].Data);
                Console.WriteLine("打印索引2处结点的路径:{0}", bt.GetPath(bt[2]));
                Console.WriteLine("打印值为ab的路径:{0}", bt.GetPath("ab")[0]);
                Console.WriteLine("打印值为e的路径:{0}", bt.GetPath("e")[0]);
                Console.WriteLine("打印值为eed的路径:{0}", bt.GetPath("eed")[0]);
                Console.WriteLine("\"a\".CompareTo(\"b\")={0}", "a".CompareTo("b"));
                Console.WriteLine("\"b\".CompareTo(\"c\")={0}", "b".CompareTo("c"));
                Console.WriteLine("\"a\".CompareTo(\"c\")={0}", "a".CompareTo("c"));
                Console.WriteLine("\"c\".CompareTo(\"a\")={0}", "c".CompareTo("a"));
                Console.WriteLine("\"a\".CompareTo(\"ab\")={0}", "a".CompareTo("ab"));
            }
            [TestMethod]
            public void AvlTest1() {
                var bt = new ArithCollect.AvlTree<string>();
                bt.Add("a");
                bt.Add("ab");
                bt.Add("b");
                bt.Add("c");
                bt.Add("e");
                bt.Add("eed");
                var len = bt.Count;
                for (int i = 0; i < len; i++) {
                    Console.WriteLine("第{0}个节点 value={1}, path = {2}", i, bt[i].Data, bt.GetPath(bt[i]));
                }
            }
            [TestMethod]
            public void AvlTest2() {
                var bt = new ArithCollect.AvlTree<int>();
                var x = 8.AdagunSet();
                foreach (var item in x) {
                    bt.Add(item);
                }
                Console.WriteLine("前序");
                foreach (var item in bt.Query(bt.Root, TreeTraversalType.Pre)) {
                    Console.WriteLine(item);
                }
                Console.WriteLine("中序");
                foreach (var item in bt.Query(bt.Root, TreeTraversalType.In)) {
                    Console.WriteLine(item);
                }
                Console.WriteLine("后序");
                foreach (var item in bt.Query(bt.Root, TreeTraversalType.Un)) {
                    Console.WriteLine(item);
                }
                var len = bt.Count;
                for (int i = 0; i < len; i++) {
                    Console.WriteLine("第{0}个节点 value={1}, path = {2}", i, bt[i].Data, bt.GetPath(bt[i]));
                }
            }
            [TestMethod]
            public void AvlTest3_remove() {
                var x = 15.AdagunSet().ToArray();
                x.Shuffle();
                var avlt = new AvlTree<int>();
                foreach (var item in x) {
                    avlt.Add(item);
                }
                //Console.WriteLine("avlt[3]={0}; avlt[3].path={1}",avlt[3],avlt.GetPath(avlt[3]));
                //avlt.Remove(avlt[3]);
                var len = avlt.Count;
                for (int i = 0; i < len; i++) {
                    Console.WriteLine("第{0}个节点 value={1}, path = {2}", i, avlt[i].Data, avlt.GetPath(avlt[i]));
                }
            }
            [TestMethod]
            public void AvlTest4() {
                //var x = 15.AdagunSet().ToArray();
                //x.Shuffle();
                var x = new[] { 6, 2, 8, 7, 5, 11, 13, 3, 1, 14, 4, 0, 10, 9, 12 };
                var avl = new AvlTree<int>();
                foreach (var item in x) {
                    avl.Add(item);
                }
                var key = 0;
                Console.WriteLine("avlt[{0}]={1}; avlt[{2}].path={3}", key, avl[key].Data, key, avl.GetPath(avl[key]));
                avl.Remove(avl[key]);
                var len = avl.Count;
                for (int i = 0; i < len; i++) {
                    Console.WriteLine("第{0}个节点 value={1}, path = {2}", i, avl[i].Data, avl.GetPath(avl[i]));
                }
                foreach (var item in avl) {
                    Console.Write("{0} ", item);
                }
            }
            [TestMethod]
            public void AvlTest5() {
                var x = new[] { 5, 2, 10, 7, 11, 6 };
                var avl = new AvlTree<int>();
                foreach (var item in x) {
                    avl.Add(item);
                }
                var len = avl.Count;
                for (int i = 0; i < len; i++) {
                    var x2 = avl[i];
                    Console.WriteLine("element:{0} value:{1} path:{2}", i, x2.Data, avl.GetPath(x2));
                }
            }
            [TestMethod]
            public void AvlTest6() {
                var x = new[] { 9, 10, 6, 5, 7, 8 };
                var avl = new AvlTree<int>();
                foreach (var item in x) {
                    avl.Add(item);
                }
                var len = avl.Count;
                for (int i = 0; i < len; i++) {
                    var x2 = avl[i];
                    Console.WriteLine("element:{0} value:{1} path:{2}", i, x2.Data, avl.GetPath(x2));
                }
            }
            [TestMethod]
            public void bfTest1() {
                var bt = new ArithCollect.BinFinderTree<string>();
                bt.Add("a");
                bt.Add("ab");
                bt.Add("b");
                bt.Add("c");
                bt.Add("e");
                bt.Add("eed");
                var len = bt.Count;
                for (int i = 0; i < len; i++) {
                    Console.WriteLine("第{0}个节点 value={1}, path = {2}", i, bt[i].Data, bt.GetPath(bt[i]));
                }
            }
        }
    }
    //http://blog.sina.com.cn/s/blog_4a9f267d0100tnjp.html
    namespace AntSystem2 {
        public class AntSystem {
            /**/
            /// <summary>
            /// 对信息量重视程度
            /// </summary>
            private int alpha;
            /**/
            /// <summary>
            /// 启发式信息受重视程度
            /// </summary>
            private int beta;
            /**/
            /// <summary>
            /// 信息素挥发速度
            /// </summary>
            private double lo;
            /**/
            /// <summary>
            /// 城市距离矩阵
            /// </summary>
            private double[,] City;
            /**/
            /// <summary>
            /// 信息素矩阵
            /// </summary>
            private double[,] Message;
            /**/
            /// <summary>
            /// opneList用于存放下步行城市
            /// </summary>
            private Queue<int> openList = new Queue<int>();
            /**/
            /// <summary>
            /// closedList用于存放已经访问过城市
            /// </summary>
            private Queue<int> closedList = new Queue<int>();
            /**/
            /// <summary>
            /// 储存较好路径
            /// </summary>
            private Queue<int> BestList = new Queue<int>();
            private int Pro_time = 0;
            /**/
            /////////////////////////////////////////////////////////
            /// <summary>
            /// 构造函数：形成城市距离和信息素矩阵
            /// </summary>
            /// <param name="city">城市距离矩阵</param>
            /// <param name="Lo"> 信息素挥发速度</param>
            public AntSystem(double[,] city, double Lo, int Alpha, int Beta) {
                alpha = Alpha;
                beta = Beta;
                lo = Lo;
                int temp = Convert.ToInt32(Math.Sqrt(city.Length));
                City = new double[temp, temp];
                Message = new double[temp, temp];
                for (int i = 0; i < temp; i++) {
                    for (int j = 0; j < temp; j++) {
                        City[i, j] = city[i, j];
                    }
                }
                //初始化信息素矩阵
                for (int i = 0; i < temp; i++) {
                    for (int j = 0; j < temp; j++) {
                        if (i != j) {
                            Message[i, j] = (double)1 / (temp * temp - temp);
                        }
                    }
                }
            }
            /**/
            ////////////////////////////////////////////////////////////
            /// <summary>
            /// 改变信息素矩阵closed_list较好路径
            /// </summary>
            /// <param name="closed_list"></param>
            private void Change_Message(Queue<int> closed_list) {
                lock (this) {
                    int[] temp_Array = new int[closed_list.Count];
                    temp_Array = closed_list.ToArray();
                    for (int i = 0; i < closed_list.Count - 1; i++) {
                        Message[temp_Array[i], temp_Array[i + 1]] = Message[temp_Array[i], temp_Array[i + 1]] + lo / ((1 - lo) * Convert.ToInt32(Get_Weight(closed_list) + 1));
                    }
                    Message[temp_Array[temp_Array.Length - 1], temp_Array[0]] = Message[temp_Array[temp_Array.Length - 1], temp_Array[0]] + lo / ((1 - lo) * Convert.ToInt32(Get_Weight(closed_list)));
                    for (int i = 0; i < closed_list.Count; i++) {
                        for (int j = 0; j < closed_list.Count; j++) {
                            Message[i, j] = (1 - lo) * Message[i, j];
                        }
                    }
                }
            }
            /**/
            ///////////////////////////////////////////////////////////////
            /// <summary>
            /// 输入链表计算出其对应总路径
            /// </summary>
            /// <param name="closed_list"></param>
            /// <returns></returns>
            public double Get_Weight(Queue<int> closed_list) {
                lock (this) {
                    double sum = 0;
                    int[] temp_Array = new int[closed_list.Count];
                    temp_Array = closed_list.ToArray();
                    for (int i = 0; i < Convert.ToInt32(temp_Array.Length) - 1; i++) {
                        sum = sum + City[temp_Array[i], temp_Array[i + 1]];
                    }
                    sum = sum + City[temp_Array[temp_Array.Length - 1], temp_Array[0]];
                    return sum;
                }
            }
            /**/
            //////////////////////////////////////////////////////////////
            /// <summary>
            /// 产生i城市下走城市集合并城市编号加入openList
            /// 产生城市已经存closedList
            /// </summary>
            /// <param name="i"></param>
            private void NextCity() {
                openList.Clear();
                int temp_int = Convert.ToInt32(Math.Sqrt(City.Length));
                for (int i = 0; i < temp_int; i++) {
                    if (closedList.Contains(i) == false) {
                        openList.Enqueue(i);
                    }
                }
            }
            /**/
            //////////////////////////////////////////////////////////////
            /// <summary>
            /// 选择应该走条路选择完路A清空openList再把A加入openList
            /// </summary>
            /// <returns></returns>
            private int choiceRoute() {
                int index = 0;//记录选择城市
                Random random = new Random();
                double random_value = (double)random.NextDouble();//随机选择概率
                int[] temp_Array = new int[openList.Count];
                temp_Array = openList.ToArray();
                double sum_Message = 0;//openList所有节点总信息量
                for (int i = 0; i < openList.Count; i++) {
                    double eta = 1 / City[Pro_time, temp_Array[i]];
                    sum_Message = sum_Message + Math.Pow(Message[Pro_time, temp_Array[i]], alpha) * Math.Pow(eta, beta);
                }
                double temp = 0;
                for (int j = 0; j < openList.Count; j++) {
                    double eta = 1 / City[Pro_time, temp_Array[j]];
                    temp = temp + Math.Pow(Message[Pro_time, temp_Array[j]], alpha) * Math.Pow(eta, beta) / sum_Message;
                    if (temp > random_value) {
                        index = temp_Array[j];
                        break;
                    }
                }
                openList.Clear();
                openList.Enqueue(index);
                return index;
            }
            /**/
            /////////////////////////////////////////////////////////////
            public Queue<int> Main_DW() {
                BestList.Clear();
                /**/
                ///共循环20次
                for (int i = 0; i < 4; i++) {
                    /**/
                    ///共有n只蚂蚁n=City'number Convert.ToInt32(Math.Sqrt(City.Length))
                    for (int j = 0; j < Convert.ToInt32(Math.Sqrt(City.Length)); j++) {
                        openList.Enqueue(0);
                        closedList.Clear();
                        while (openList.Count != 0 && closedList.Count != Convert.ToInt32(Math.Sqrt(City.Length))) {
                            int temp = openList.Dequeue();
                            Pro_time = temp;
                            closedList.Enqueue(temp);
                            if (openList.Count == 0 && closedList.Count == Convert.ToInt32(Math.Sqrt(City.Length))) {
                                if (BestList.Count == 0) {
                                    int[] temp_Array = new int[Convert.ToInt32(Math.Sqrt(City.Length))];
                                    temp_Array = closedList.ToArray();
                                    for (int k = 0; k < Convert.ToInt32(Math.Sqrt(City.Length)); k++) {
                                        BestList.Enqueue(temp_Array[k]);
                                    }
                                }
                                if (Get_Weight(BestList) > Get_Weight(closedList)) {
                                    BestList.Clear();
                                    int[] temp_Array = new int[Convert.ToInt32(Math.Sqrt(City.Length))];
                                    temp_Array = closedList.ToArray();
                                    for (int k = 0; k < Convert.ToInt32(Math.Sqrt(City.Length)); k++) {
                                        BestList.Enqueue(temp_Array[k]);
                                    }
                                }
                            }
                            NextCity();
                            choiceRoute();
                        }
                    }
                    Change_Message(BestList);//修改信息量
                }
                return BestList;
            }
        }
    }
    namespace AntSystem {
        [TestClass]
        public class MyTestClass {
            [TestMethod]
            public void MyTestMethod() {
                var links = new List<Link>();
                var ran = new Random();
                for (int i = 0; i < 20; i++) {
                    links.Add(new Link(i + 1, ran.Next(150), ran.Next(150), ran.Next(1000) + ran.NextDouble(), ran.Next(100) + ran.NextDouble()));
                }
                var antsys = new AntSys(2, 54, links);
                antsys.Search();
            }
        }
        public class AntSys {
            private int _antNum;
            private int _maxTimes;
            private List<Link> _links;
            private int _Id;
            private int _Start;
            private int _End;
            private Dictionary<int, List<int>> Ant_traces;
            public AntSys(int start, int end, List<Link> lnks) {
                _Start = start;
                _End = end;
                _links = lnks;
                Ant_traces = new Dictionary<int, List<int>>();
                Search();
            }
            public void Search() {
                for (int i = 1; i <= 200; i++) {
                    Ant ant = new Ant(i, _Start, _End, _links);
                    List<int> trace = ant.GetTrace();
                    Ant_traces.Add(i, trace);
                }
            }
            public Dictionary<int, List<int>> GetAntTraces() {
                return Ant_traces;
            }
        }
        public class Ant {
            private int _Id;
            private int _Start;
            private int _End;
            private List<int> _Traces;
            private List<Link> _Links;
            private Dictionary<int, List<int>> _NotAvaNodes = new Dictionary<int, List<int>>();
            private int _Resent;
            public Ant(int id, int start, int end, List<Link> lnks) {
                _Id = id;
                _Start = start;
                _End = end;
                _Links = lnks;
                _Resent = start;
                _Traces = new List<int>();
                _Traces.Add(_Start);
                FindRoute();
            }
            public void FindRoute() {
                while (_Resent != _End) {
                    // 得到可选路径
                    List<Link> links = GetViableRoutes();
                    // 假如数据链路表为空，返回一步
                    if (links.Count == 0) {
                        GoBack();
                    }
                        // 选择线路
                    else {
                        ChooseRoute(links);
                        _Traces.Add(_Resent);
                    }
                }
            }
            protected List<Link> GetViableRoutes() {
                List<Link> links = _Links.FindAll(delegate(Link lnk) { return lnk.StartId == _Resent && !_Traces.Contains(lnk.EndId); });
                if (_NotAvaNodes.ContainsKey(_Resent)) {
                    List<int> bad_nodes = _NotAvaNodes[_Resent];
                    foreach (int bad_node in bad_nodes) {
                        Link badlink = links.Find(delegate(Link l) { return l.StartId == _Resent && l.EndId == bad_node; });
                        if (badlink != null)
                            links.Remove(badlink);
                    }
                }
                return links;
            }
            protected void GoBack() {
                int bad_node = _Resent;
                _Traces.Remove(_Resent);
                _Resent = _Traces[_Traces.Count - 1];
                if (_NotAvaNodes.ContainsKey(_Resent)) {
                    _NotAvaNodes[_Resent].Add(bad_node);
                } else {
                    List<int> bad_nodes_list = new List<int>();
                    bad_nodes_list.Add(bad_node);
                    _NotAvaNodes.Add(_Resent, bad_nodes_list);
                }
            }
            protected void ChooseRoute(List<Link> links) {
                Thread.Sleep(10);
                Random rand = new Random();
                double radio = rand.NextDouble();
                double sum = 0;
                double temp = 0;
                links.ForEach(delegate(Link l) { sum += l.Hormone; });
                foreach (Link lnk in links) {
                    temp += lnk.Hormone;
                    if (temp / sum >= radio) {
                        _Resent = lnk.EndId;
                        break;
                    }
                }
            }
            public List<int> GetTrace() {
                return _Traces;
            }
        }
        public class Link {
            public int Id;
            public int StartId;
            public int EndId;
            public double LinkValue;
            public double Hormone;
            public Link() {
            }
            public Link(int id, int start, int end, double value, double hormone) {
                this.Id = id;
                this.StartId = start;
                this.EndId = end;
                this.LinkValue = value;
                this.Hormone = hormone;
            }
        }
    }
    namespace Dijkstra {
        [TestClass]
        public class DijkstraSample {
            static int length = 6;
            static string[] shortedPath = new string[length];
            static int noPath = 2000;
            static int MaxSize = 1000;
            //static int[,] G = { { noPath, noPath, 10, noPath, 30, 100 }, { noPath, noPath, 5, noPath, noPath, noPath }, { noPath, noPath, noPath, 50, noPath, noPath }, { noPath, noPath, noPath, noPath, noPath, 10 }, { noPath, noPath, noPath, 20, noPath, 60 }, { noPath, noPath, noPath, noPath, noPath, noPath } };
            static int[,] G = {
                          { noPath, 6, 3, noPath, noPath, noPath },
                          { 6, noPath, 2, 5, noPath, noPath },
                          { 3, 2, noPath, 3, 4, noPath },
                          { noPath, 5, 3, noPath, 2, 3 },
                          { noPath, noPath, 4,2, noPath,5 },
                          { noPath, noPath, noPath, 3, 5, noPath }
                          };
            static string[] PathResult = new string[length];

            static int[] path1 = new int[length];
            static int[,] path2 = new int[length, length];
            static int[] distance2 = new int[length];
            [TestMethod]
            public void DijkstraTest() {
                int dist1 = getShortedPath(G, 0, 5, path1);
                Console.WriteLine("点0到点5路径:");
                for (int i = 0; i < path1.Length; i++)
                    Console.Write(path1[i].ToString() + " ");
                Console.WriteLine("长度:" + dist1);

                int[] pathdist = getShortedPath(G, 0, path2);
                Console.WriteLine("点0到任意点的路径:");
                for (int j = 0; j < pathdist.Length; j++) {
                    Console.WriteLine("点0到" + j + "的路径:");
                    for (int i = 0; i < length; i++)
                        Console.Write(path2[j, i].ToString() + " ");
                    Console.WriteLine("长度:" + pathdist[j]);
                }

                Console.ReadKey();
            }

            //从某一源点出发，找到到某一结点的最短路径
            static int getShortedPath(int[,] G, int start, int end, int[] path) {
                bool[] s = new bool[length]; //表示找到起始结点与当前结点间的最短路径
                int min;   //最小距离临时变量
                int curNode = 0; //临时结点，记录当前正计算结点
                int[] dist = new int[length];
                int[] prev = new int[length];

                //初始结点信息
                for (int v = 0; v < length; v++) {
                    s[v] = false;
                    dist[v] = G[start, v];
                    if (dist[v] > MaxSize)
                        prev[v] = 0;
                    else
                        prev[v] = start;
                }
                path[0] = end;
                dist[start] = 0;
                s[start] = true;
                //主循环
                for (int i = 1; i < length; i++) {
                    min = MaxSize;
                    for (int w = 0; w < length; w++) {
                        if (!s[w] && dist[w] < min) {
                            curNode = w;
                            min = dist[w];
                        }
                    }

                    s[curNode] = true;

                    for (int j = 0; j < length; j++)
                        if (!s[j] && min + G[curNode, j] < dist[j]) {
                            dist[j] = min + G[curNode, j];
                            prev[j] = curNode;
                        }

                }
                //输出路径结点
                int e = end, step = 0;
                while (e != start) {
                    step++;
                    path[step] = prev[e];
                    e = prev[e];
                }
                for (int i = step; i > step / 2; i--) {
                    int temp = path[step - i];
                    path[step - i] = path[i];
                    path[i] = temp;
                }
                return dist[end];
            }

            //从某一源点出发，找到到所有结点的最短路径
            static int[] getShortedPath(int[,] G, int start, int[,] path) {
                int[] PathID = new int[length];//路径（用编号表示）
                bool[] s = new bool[length]; //表示找到起始结点与当前结点间的最短路径
                int min;   //最小距离临时变量
                int curNode = 0; //临时结点，记录当前正计算结点
                int[] dist = new int[length];
                int[] prev = new int[length];
                //初始结点信息

                for (int v = 0; v < length; v++) {
                    s[v] = false;
                    dist[v] = G[start, v];
                    if (dist[v] > MaxSize)
                        prev[v] = 0;
                    else
                        prev[v] = start;
                    path[v, 0] = v;
                }

                dist[start] = 0;
                s[start] = true;
                //主循环
                for (int i = 1; i < length; i++) {
                    min = MaxSize;
                    for (int w = 0; w < length; w++) {
                        if (!s[w] && dist[w] < min) {
                            curNode = w;
                            min = dist[w];
                        }
                    }

                    s[curNode] = true;

                    for (int j = 0; j < length; j++)
                        if (!s[j] && min + G[curNode, j] < dist[j]) {
                            dist[j] = min + G[curNode, j];
                            prev[j] = curNode;
                        }

                }
                //输出路径结点
                for (int k = 0; k < length; k++) {
                    int e = k, step = 0;
                    while (e != start) {
                        step++;
                        path[k, step] = prev[e];
                        e = prev[e];
                    }
                    for (int i = step; i > step / 2; i--) {
                        int temp = path[k, step - i];
                        path[k, step - i] = path[k, i];
                        path[k, i] = temp;
                    }
                }
                return dist;

            }
        }
    }
    /*
    * 求最小生成树，采用Prim算法
    * @author henterji
    */
    namespace Prime {
        /**
        * 边
        */
        class Edge {
            /**
            * 边的起点
            */
            public char vexa;
            /**
            * 边的终点
            */
            public char vexb;
            /**
            * 边的权植
            */
            public int weight;
            public Edge(char vexa, char vexb, int weight) {
                this.vexa = vexa;
                this.vexb = vexb;
                this.weight = weight;
            }
        }
        [TestClass]
        public class MST {
            /**
            * 初始化图
            */
            static Edge[] e = { new Edge('a', 'b', 2), new Edge('b', 'c', 1),
        new Edge('c', 'd', 2), new Edge('d', 'e', 9),
        new Edge('e', 'f', 4), new Edge('f', 'g', 1),
        new Edge('g', 'h', 9), new Edge('h', 'a', 1),
        new Edge('a', 'i', 8), new Edge('b', 'i', 6),
        new Edge('c', 'j', 3), new Edge('d', 'k', 7),
        new Edge('e', 'k', 2), new Edge('f', 'k', 1),
        new Edge('g', 'j', 4), new Edge('h', 'i', 7),
        new Edge('i', 'j', 1), new Edge('j', 'k', 6) };

            /**
            * w函数
            * @param x 起点序号
            * @param y 终点序号
            * @return 返回起点序号为x，终点序号为y的边的权植。如果没有这条边就返回无穷大
            */
            static int w(int x, int y) {
                char from = (char)(x + 97);
                char to = (char)(y + 97);
                for (int i = 0; i < 18; i++) {
                    if (e[i].vexa == from && e[i].vexb == to) {
                        return e[i].weight;
                    }
                    if (e[i].vexa == to && e[i].vexb == from) {
                        return e[i].weight;
                    }
                }
                return 1000; // 用1000代表无穷大，如果图中没有这条边就返回无穷大
            }
            [TestMethod]
            public void PrimTest1() {

                //Edge[] e_mst = new Edge[10]; // 表示已经加入最小生成树的边

                // 表示已经加入最小生成树(mst)的结点, 数组元素从0到10分别对应结点a到j
                // 如果vex_mst=0，表示对应结点没有加入到mst
                // 如果vex_mst=1，表示对应结点已经加入到mst
                int[] vex_mst = new int[11];

                for (int i = 0; i < 11; i++)
                    // 初始化
                    vex_mst[i] = 0;

                vex_mst[0] = 1; // 设置初始结点为a

                // 将10条边加入到最小生成树
                for (int i = 0; i < 10; i++) {
                    // 加入一条边。
                    // 这条边的两个结点一个在mst中，而另一个不在mst中而且具有最小权植
                    int add_vex = 0; // 选中的结点
                    int min_weight = 1000; // 最小权植,初始值为1000
                    Edge adde = new Edge(' ', ' ', 0);
                    for (int j = 0; j < 11; j++)
                        if (vex_mst[j] == 1) { // j是mst中的结点
                            for (int k = 0; k < 11; k++) {
                                if (vex_mst[k] == 0 && w(j, k) < min_weight) {
                                    add_vex = k;
                                    min_weight = w(j, k);
                                    adde.vexa = (char)(j + 97);
                                    adde.vexb = (char)(k + 97);
                                    adde.weight = min_weight;
                                }
                            }
                        }
                    vex_mst[add_vex] = 1; // 将选择的结点加入mst
                    char avex = (char)(add_vex + 97); // 将选择的边加入mst
                    Console.WriteLine("addvex:" + avex);
                    // 输出加入mst的顶点，边，以及边的权植
                    Console.WriteLine("addedge:" + adde.vexa + "-" + adde.vexb + " w:"
                        + adde.weight);
                }
            }
        }

    }
    //
    namespace kruskal {
        public class kruskal {
            public int maxbian = 11;
            public int maxdingdian = 10;
            public struct edge {
                public int vex1;                     //边的起始顶点
                public int vex2;                      //边的终止顶点
                public int weight;                    //边的权值
            }
            public void kruskalmethod(edge[] E, int n, int e) {
                int i, j, m1, m2, sn1, sn2, k;
                int[] vset = new int[maxdingdian];
                for (i = 1; i <= n; i++)        //初始化辅助数组
                    vset[i] = i;
                k = 1;        //表示当前构造最小生成树的第k条边，初值为1
                j = 0;                   //E中边的下标，初值为0
                while (k < e) {             //生成的边数小于e时继续循环
                    m1 = E[j].vex1;
                    m2 = E[j].vex2;//取一条边的两个邻接点
                    sn1 = vset[m1];
                    sn2 = vset[m2];
                    //分别得到两个顶点所属的集合编号
                    if (sn1 != sn2)
                    //两顶点分属于不同的集合，该边是最小生成树的一条边      
                {
                        //int temp=E [j].weight
                        Console.WriteLine("{0},{1},{2}", m1, m2, E[j].weight);
                        k++;                //生成边数增l
                        if (k >= 6) break;
                        for (i = 1; i <= n; i++)    //两个集合统一编号
                            if (vset[i] == sn2)  //集合编号为sn2的改为sn1
                                vset[i] = sn1;
                    }//if                j++;                  //扫描下一条边
                }//while
            }//kruskal
            public void me() {
                edge[] E = new edge[maxbian];
                int nume, numn;
                nume = 5;
                numn = 7;
                E[0].vex1 = 4;
                E[0].vex2 = 5;
                E[0].weight = 10;
                E[1].vex1 = 1;
                E[1].vex2 = 4;
                E[1].weight = 20;
                E[2].vex1 = 1;
                E[2].vex2 = 2;
                E[2].weight = 60;
                E[3].vex1 = 5;
                E[3].vex2 = 3;
                E[3].weight = 70;
                E[4].vex1 = 2;
                E[4].vex2 = 3;
                E[4].weight = 80;
                E[5].vex1 = 2;
                E[5].vex2 = 4;
                E[5].weight = 95;
                E[6].vex1 = 2;
                E[6].vex2 = 3;
                E[6].weight = 100;
                kruskalmethod(E, numn, nume);
            }
        }
        [TestClass]
        public class Program {
            [TestMethod]
            public void kruskal_Test() {
                kruskal kru = new kruskal();
                kru.me();
                Console.Read();
            }
        }

    }
    //http://blog.sina.com.cn/s/blog_4ed027020100c9ln.html
    namespace pso {
        [TestClass]
        public class MyPSO {
            const int NUM = 40;//粒子数
            const int DIM = 30;//维数
            const double c1 = 1.8;//参数
            const double c2 = 1.8;//参数

            static double xmin = -100.0;//位置下限
            static double xmax = 100.0;//位置上限
            static double[] gbestx = new double[DIM];//全局最优位置
            static double gbestf;//全局最优适应度
            static Random rand = new Random();//用于生成随机数
            class Particle {//定义一个粒子
                public double[] x = new double[DIM];//当前位置矢量
                public double[] bestx = new double[DIM];//历史最优位置
                public double f;//当前适应度
                public double bestf;//历史最优适应度
            }
            Particle[] swarm = new Particle[NUM];//定义粒子群
            double f1(double[] x) {//测试函数：超球函数
                return x.Sum(a => a * a);
            }

            [TestMethod]
            public void MainTest() {
                for (int i = 0; i < DIM; i++)//初始化全局最优
                    gbestx[i] = rand.NextDouble() * (xmax - xmin) + xmin;
                gbestf = double.MaxValue;
                for (int i = 0; i < NUM; i++) {//初始化粒子群
                    Particle p1 = new Particle();
                    for (int j = 0; j < DIM; j++)
                        p1.x[j] = rand.NextDouble() * (xmax - xmin) + xmin;
                    p1.f = f1(p1.x);
                    p1.bestf = double.MaxValue;
                    swarm[i] = p1;
                }
                for (int t = 0; t < 5000; t++) {
                    for (int i = 0; i < NUM; i++) {
                        Particle p1 = swarm[i];
                        for (int j = 0; j < DIM; j++)//进化方程
                            p1.x[j] += c1 * rand.NextDouble() * (p1.bestx[j] - p1.x[j])
                                + c2 * rand.NextDouble() * (gbestx[j] - p1.x[j]);
                        p1.f = f1(p1.x);
                        if (p1.f < p1.bestf) {//改变历史最优
                            p1.x.CopyTo(p1.bestx, 0);
                            p1.bestf = p1.f;
                        }
                        if (p1.f < gbestf) {//改变全局最优
                            p1.x.CopyTo(gbestx, 0);
                            for (int j = 0; j < DIM; j++)//把当前全局最优的粒子随机放到另一位置
                                p1.x[j] = rand.NextDouble() * (xmax - xmin) + xmin;
                            gbestf = p1.f;
                        }
                    }
                }
                Console.WriteLine("{0}", gbestf);
            }
        }
    }
}
